Field of the Invention
This invention relates to systems and methods for implementing a low density parity check (LDPC) decoding algorithm.
Background of the Invention
A. LDPC Codes and Min-Sum Decoding
Low-density parity-check (LDPC) codes were discovered by Gallager in 1962, and rediscovered and shown to be Shannon-limit approaching in the late 1990's. Its very low density of 1's in H matrix renders it convenient to represent an LDPC code by a bipartite graph, called a Tanner Graph. There are two types of nodes in a Tanner graph, namely, variable nodes (VN's) and check nodes (CN's). Each variable node (or check node) corresponds to a column (or row) of the parity-check matrix H. We denote by V={v1, v2, . . . vn} the set of variable nodes, and by C={c1, c2, . . . cm} the set of check nodes. We also index each row of H by ={1, 2, . . . , m} and each column of H by V={1, 2, . . . , n}. In the Tanner graph, VN vi is connected to CN cj via an edge if Hj,i=1, and the set of edges on the Tanner graph is denoted by set E (see FIGS. 4A and 4B).
Quasi-cyclic (QC) LDPC codes are a special class of the LDPC codes with structured H matrix which can be generated by the expansion of an mb×nb base matrix. Each 1's element in the base matrix can be expanded by a circularly right-shifted b×b identity sub-matrix. QC-LDPC codes have advantages over other types of LDPC codes in hardware implementations of both encoding and decoding. Encoding of a QC-LDPC code can be efficiently implemented using simple shift registers. In hardware implementation of a QC-LDPC decoder, the QC structure of the code simplifies the wire routing for message passing.
The message-passing (MP) algorithm is the most efficient to achieve near-optimal decoding of LDPC codes. We now briefly introduce the variable node (VN) and check node (CN) update rules of message passing decoding. In the sequel, for notational conciseness, we simply use i, instead of vi, to denote a VN, and, j, instead of cj, to denote a CN. A VN i receives an input message Lich from the channel, typically the log-likelihood ratio (LLR) of the corresponding channel output, defined as follows:
                              L          i          ch                =                              log            ⁡                          (                                                Pr                  ⁡                                      (                                                                  R                        i                                            =                                                                                                    r                            i                                                    |                                                      c                            i                                                                          =                        0                                                              )                                                                    Pr                  ⁡                                      (                                                                  R                        i                                            =                                                                                                    r                            i                                                    |                                                      c                            i                                                                          =                        1                                                              )                                                              )                                =          log                                    (        1        )            
where ciε{0,1} is the code bit and ri is the corresponding received symbol.
The conventional iterative MP decoder alternates between two phases, a “VN-to-CN” phase during which VN's send messages to CN's along their adjacent edges, and a “CN-to-VN” phase during which CN's send messages to their adjacent VN's. The message update rules, whose details will be given later in this section, are depicted schematically in Tables. 1 and 2, respectively. In the initialization step of the decoding process, VN i forwards the same message to all of its neighboring CN's, V(i), namely the LLR Lich derived from the corresponding channel output. In the CN-to-VN message update phase, CN j uses the incoming messages and CN update rule to compute and forward, to VN iε(j) a new “CN-to-VN” message, Lj→i. VN i then processes its incoming messages according to VN update rule and forwards to each adjacent CN, (i), an updated “VN-to-CN” message, Li→j. After a pre-specified number of iterations, VN i sums all of the incoming LLR messages to produce an estimate of the corresponding code bit i. Note that all of the “CN-to-VN” message updates can be done in parallel, as can all of the “VN-to-CN” message updates. This enables efficient, high-speed software and hardware implementations of the iterative MP decoding algorithms.
Denote by Li→j and Lj→i the messages sent from VN i to CN j and from CN j to VN i, respectively. Denote by (i) the set of CN's directly connected to VN i and V(j), the set of VN's directly connected to CN j. Then, the message sent from VN i to CN j in SPA (sum-product algorithm) decoding is given by:Li→j=Lich+Lj′→i,  (2)
and the message from CN j to VN i is computed as
                              L                      j            →            i                          =                  2          ⁢                                          ⁢                                                    tanh                                  -                  1                                            ⁡                              (                                                      Π                                                                  i                        ′                                            ∈                                                                        v                          ⁡                                                      (                            j                            )                                                                          ⁢                        \                        ⁢                                                                                                  ⁢                        i                                                                              ⁢                  tanh                  ⁢                                                            L                                                                        i                          ′                                                -                        j                                                              2                                                  )                                      .                                              (        3        )            
Denote by Pi a posterior probability (APP) message of VN i,Pi=Lich+Lj′→i  (4)
In practically prevailing min-sum decoding, a VN takes log-likelihood ratios of received information from the channel as initial input message, i.e., Li→j=Lich, and the following equivalent CN update rule is employedLj→i=[Πi′εV(j)\isign(Li′→j)]·α·(β+mini′εV(j)\i|Li′→j|),  (5)
where 0<α,β<1 are the attenuation factor and offset, respectively, which can be a fixed constant or adaptively adjusted [1]. We next introduce some notations to simplify the above calculation in the algorithmic procedure. LetSi→jsign(Li→j).  (6)
Denote by S(j) the product sign of all VN i's to the CN jS(j)Πi′εV(j)Si′→j.  (7)
Denote by Lmin1(j) and imin1(j) the normalized minimum VN message to the CN j and its associated index, respectively,Lmin1(j)α·(β+mini′εV(j)|Li′→j|),imin1(j)arg mini′εV(j)|Li′→j|  (8)
and by Lmin2(j) the normalized second minimum VN message to the CN j
                              L                      m            ⁢                                                  ⁢            i            ⁢                                                  ⁢            n            ⁢                                                  ⁢            2                                (            j            )                          ⁢                  =          Δ                ⁢                  α          ·                      (                          β              +                                                min                                                            i                      ⁢                                                                                          ⁢                      ′                                        ∈                                                                  𝒱                        ⁡                                                  (                          j                          )                                                                    ⁢                      \                      ⁢                                                                                          ⁢                                              i                                                  m                          ⁢                                                                                                          ⁢                          i                          ⁢                                                                                                          ⁢                          n                          ⁢                                                                                                          ⁢                          1                                                                          (                          j                          )                                                                                                                    ⁢                                                                        L                                                                  i                        ⁢                                                                                                  ⁢                        ′                                            ->                      j                                                                                                              )                                              (        9        )            
With the above notations, (5) is conveniently re-expressed by
                              L                      j            ->            i                          =                              S                          (              j              )                                ·                      S                          i              ->              j                                ·                      {                                                                                L                                          m                      ⁢                                                                                          ⁢                      i                      ⁢                                                                                          ⁢                      n                      ⁢                                                                                          ⁢                      1                                                              (                      j                      )                                                                                                                                  if                      ⁢                                                                                          ⁢                      i                                        ≠                                          i                                              m                        ⁢                                                                                                  ⁢                        i                        ⁢                                                                                                  ⁢                        n                        ⁢                                                                                                  ⁢                        1                                                                    (                        j                        )                                                                                                                                                              L                                          m                      ⁢                                                                                          ⁢                      i                      ⁢                                                                                          ⁢                      n                      ⁢                                                                                          ⁢                      2                                                              (                      j                      )                                                                                                                                  if                      ⁢                                                                                          ⁢                      i                                        =                                          i                                              m                        ⁢                                                                                                  ⁢                        i                        ⁢                                                                                                  ⁢                        n                        ⁢                                                                                                  ⁢                        1                                                                    (                        j                        )                                                                                                                                                    (        10        )            
A hardware amenable min-sum decoding algorithm is described in Algorithm 1 of Table 1.
TABLE 1Flooding Min-Sum DecodingAlgorithm 1 Flooding Min-Sum DecodingIntialization: Lmin1(j) = Lmin2(j) = 0, ∀j ε   Iteration: 1:for ∀i ε V, do 2: for ∀j ε   (i), do 3:  Read (old) {S(j), imin1(j), Lmin1(j), Lmin2(j)}  4:        Compute    ⁢                  ⁢          L              j        →        i              ←      {                                                                      S                                  (                  j                  )                                            ·                              S                                  i                  →                  j                                            ·                              L                                  min                  ⁢                                                                          ⁢                  1                                                  (                  j                  )                                                      ,                                                              if              ⁢                                                          ⁢              i                        ≠                          i                              min                ⁢                                                                  ⁢                1                                            (                j                )                                                                                                                    S                                  (                  j                  )                                            ·                              S                                  i                  →                  j                                            ·                              L                                  min                  ⁢                                                                          ⁢                  2                                                  (                  j                  )                                                      ,                                                              if              ⁢                                                          ⁢              i                        =                          i                              min                ⁢                                                                  ⁢                1                                            (                j                )                                                          5: end for 6: Compute Pi ← Lich +   Lj→i 7: for ∀j ε   (i), do 8:  Compute Li→j ← Pi − Lj→i 9:  Store Si→j ← sign (Li→j)10:  Update CN j's new information, {S(j), imin1(j), Lmin1(j), Lmin2(j)},  with respect to Li→j.11: end for12:end for13:Store all {S, imin1, Lmin1, Lmin2}14:If the hard-decision of [P1, P2, . . . , Pn] yields the all-zero syndrome, then terminate
When a QC-LDPC code with b×b circulants is in use, each circulant of b bits are updated independently and in parallel. In [5], a new non-uniform quantization method was proposed to extend the message quantization range by using exponentially increased step size for large magnitudes while keeping fixed step size for small magnitudes. However, the proposed exponentially increased step size design is difficult for hardware implementation.
B. Layered Min-Sum Decoding
In the hardware implementation of iterative MP decoding, the decoding efficiency can be further improved by the layered decoding approach [2]-[4]. The layered decoding is based on a serial update of CN messages. Instead of sending all messages from VN's to CN's, and then all messages from CN's to VN's, the layered coding go over the CN's in sequential order such that, to each updating CN, all messages are sent in and processed, and then sent out to neighboring VN's. Such scheduled serial updates on CN's enables immediate propagation of the newly updated message; unlike the conventional flooding scheme where the updated messages can propagate only in next iteration.
The layered decoding roughly increases convergence speed by twice over the conventional flooding implementation. Moreover, it provides a good trade-off between speed and memory [3], [4]. This is achieved by iterating over dynamic CN-to-VN messages, denoted by Q{q1, Q2, . . . , Qn]. Specifically, let VN iεV(j), then Qi over a layer j is defined asQi(j)Lj→i=Lich+Lj′→i(last),  (11)
where the superscript(last) denotes the latest updated. It is worth noting that, in layered decoding the VN-to-CN message updated at the last layer (all but the last are from the current iteration) is utilized to update the CN-to-VN Qi in the current layer, whereas in the conventional flooding decoding updating a CN-to-VN message Lj→i utilizes the VN-to-CN messages each generated at the last iteration. Q  {Q1, Q2, . . . , Qn] memory is initialized with the channel messages Lch [L1ch, L2ch, . . . , Lnch], and no dedicated memory is needed to store Lch, whereas in flooding method, Lch is stored but not Q. Qi, i=1, 2, . . . , n, is iteratively calculated as follows. Let j be the current layer and ji be the preceding layer associated with VN i (herein a preceding layer is mathematically declared as follows. Let j1<j2< . . . <jk be all CN's directly connected of VN i, then jl is the preceding layer of jl+1 for l=1, 2, . . . , k−1, and jk is the preceding layer of j1.).
The APP (a-posterior probability) message Pi at the layer j is calculated asPi(j)=Qi(ji)+Lji→inew  (12)
where Lji→inew is newly updated and Qi is iteratively updated byQi(j)=Pi(j)−Lj→iold,  (13)
where Lj→iold was updated exactly one iteration back. The layered decoding can be applied to all types of iterative MP (message passing) decoding, including SAP and min-sum decoding. A hardware amenable layered min-sum decoding algorithm is described in Table 2.
TABLE 2Layered Min-Sum Decoding.Algorithm 2 Layered Min-Sum DecodingInitialization: Lmin1(j) = Lmin2(j) = 0, ∀j ε   ; Qi = Lich, ∀i ε V;   = 0Iteration: 1:for ∀j ε   do 2: for ∀i ε V(j) do 3:  Read (new) {S(ji), imin1(ji), Lmin1(ji), Lmin2(ji)},  where ji is the preceding layer of VN i  4:        Compute    ⁢                  ⁢          L                        j          i                →        i            new        ←      {                                                                      S                                  (                                      j                    i                                    )                                            ·                              S                                  i                  →                                      j                    i                                                              ·                              L                                  min                  ⁢                                                                          ⁢                  1                                                  (                                      j                    i                                    )                                                      ,                                                              if              ⁢                                                          ⁢              i                        ≠                          i                              min                ⁢                                                                  ⁢                1                                            (                                  j                  i                                )                                                                                                                    S                                  (                                      j                    i                                    )                                            ·                              S                                  i                  →                                      j                    i                                                              ·                              L                                  min                  ⁢                                                                          ⁢                  2                                                  (                                      j                    i                                    )                                                      ,                                                              if              ⁢                                                          ⁢              i                        =                          i                              min                ⁢                                                                  ⁢                1                                            (                                  j                  i                                )                                                          5:  Compute Pi ← Qi + Lji→inew 6:  Read (old) {S(j), imin1(j), Lmin1(j), Lmin2(j)}.  7:        Compute    ⁢                  ⁢          L              j        →        i            old        ←      {                                                                      S                                  (                  j                  )                                            ·                              S                                  i                  →                  j                                            ·                              L                                  min                  ⁢                                                                          ⁢                  1                                                  (                  j                  )                                                      ,                                                              if              ⁢                                                          ⁢              i                        ≠                          i                              min                ⁢                                                                  ⁢                1                                            (                j                )                                                                                                                    S                                  (                  j                  )                                            ·                              S                                  i                  →                  j                                            ·                              L                                  min                  ⁢                                                                          ⁢                  2                                                  (                  j                  )                                                      ,                                                              if              ⁢                                                          ⁢              i                        =                          i                              min                ⁢                                                                  ⁢                1                                            (                j                )                                                          8:  Compute Qi ← Pi − Lj→iold. 9:  Store Si→j = sign(Qi)10:  Update CN j's new information, {S(j), imin1(j), Lmin1(j), Lmin2(j)},  with respect to (Qi).11: end for12: Store {S(j), imin1(j), Lmin1(j), Lmin2(j)}13:end for14:If the hard-decision of [P1, P2, . . . , Pn] yields the all-zero syndrome, then stop.15:Circularly increase layer number   by 1.
When a QC-LDPC code with b×b circulants is in use, b QC rows of H is naturally treated as a layer, that is, a layer contains b CN's, each being updated independently and in parallel.
The systems and methods disclosed herein provide an improved approach for performing LDPC decoding using Tanner graphs.